/*
 * podzial.cpp
 *
 * Version: $Id: podzial.cpp 44 2011-10-29 06:34:59Z s8376@pjwstk.edu.pl $
 */
#include <iostream>
#include <math.h>
using namespace std;

bool isPrimeNumber(int n)
{
    if (n <= 1) {
        return false;
    }

    int r = sqrt(n);
    int i = 2;

    while (i <= r) {
        if (!(n % i++)) {
            return false;
        }
    }

    return true;
}
void podzial(int* A, int dlugoscA)
{
    bool changeFlag;
    int buffer;

    while (true) {
        changeFlag = false;

        for (int i = 0; i < dlugoscA - 1; i++) {
            if (
                (!isPrimeNumber(A[i]) && (isPrimeNumber(A[i + 1])))
                || (
                        (!isPrimeNumber(A[i]) && !isPrimeNumber(A[i + 1]))
                        || (isPrimeNumber(A[i]) && isPrimeNumber(A[i + 1]))
                 ) && (A[i] > A[i + 1])
            ) {
                buffer = A[i];
                A[i] = A[i + 1];
                A[i + 1] = buffer;

                changeFlag = true;
            }
        }
        if (!changeFlag) { // jezeli nie nastapila zmiana
            break;
        }
    }

    for (int i = 0; i < dlugoscA; i++) {
        cout << A[i] << " ";
    }
    cout << endl;

}
